Вот часть некоторой грамматики: B ::= |AB. Фактически, это обычное регулярное повторение B ::= A*.
При любом параллельном разборе такой части грамматики мы получаем O((длина последовательности A)2) количество промежуточных вариантов разбора. Можно и куб получить, в общем, нехорошо получается.
В статье про
параллельный разбор разумных грамматик
(
Read more... )